{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #整数反转"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 32 位的有符号整数 <code>x</code> ，返回将 <code>x</code> 中的数字部分反转后的结果。</p>\n",
    "\n",
    "<p>如果反转后整数超过 32 位的有符号整数的范围 <code>[−2<sup>31</sup>,  2<sup>31 </sup>− 1]</code> ，就返回 0。</p>\n",
    "<strong>假设环境不允许存储 64 位整数（有符号或无符号）。</strong>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 123\n",
    "<strong>输出：</strong>321\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = -123\n",
    "<strong>输出：</strong>-321\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 120\n",
    "<strong>输出：</strong>21\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>x = 0\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-2<sup>31</sup> <= x <= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-integer](https://leetcode.cn/problems/reverse-integer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-integer](https://leetcode.cn/problems/reverse-integer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['123', '-123', '120']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumOfPower(self, a: List[int]) -> int:\n",
    "        mod=10**9+7\n",
    "        a.sort()\n",
    "        n=len(a)\n",
    "        b=[1]*n\n",
    "        for i in reversed(range(n)):\n",
    "            b[i]=a[i]*pow(2,n-i-1,mod)%mod\n",
    "        print(b)\n",
    "        c=ans=0\n",
    "        for i in range(n):\n",
    "            ans+=pow(a[i],3,mod)\n",
    "            if i>0:\n",
    "                ans=(ans+c*pow(pow(2,n-i,mod),mod-2,mod)%mod*a[i]*a[i]%mod)%mod\n",
    "            c=(c+b[i])%mod\n",
    "            # print(i,c,ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 回溯安排\n",
    "        def dfs(pos,res):\n",
    "            if n == pos:\n",
    "                ans.append(res[:])\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(pos + 1,res)\n",
    "            # 选\n",
    "            res.append(nums[pos])\n",
    "            dfs(pos + 1,res)\n",
    "            res.pop()\n",
    "\n",
    "        n = len(nums)\n",
    "        nums.sort(reverse=False)\n",
    "        ans = list()\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def powerfulIntegers(x: int, y: int, bound: int) -> List[int]:\n",
    "        import math\n",
    "        if bound ==0:\n",
    "            return []\n",
    "        if x != 1:\n",
    "            v1 = [x ** i for i in range(int(math.log(bound, x)) + 1)]\n",
    "        else:\n",
    "            v1 = [1]\n",
    "        if y != 1:\n",
    "            v2 = [y ** j for j in range(int(math.log(bound, y)) + 1)]\n",
    "        else:\n",
    "            v2 = [1]\n",
    "        v2.reverse()\n",
    "        i, j = 0, 0\n",
    "        ans = []\n",
    "        while 0 <= i < len(v1) and 0 <= j < len(v2):\n",
    "            if v1[i] + v2[j] <= bound:\n",
    "                if j > 0 and bound < v1[i] + v2[j - 1]:\n",
    "                    ans.extend([v1[i] + v2[k] for k in range(j, len(v2))])\n",
    "                    i += 1\n",
    "                elif j == 0:\n",
    "                    ans.extend([v1[i] + v2[k] for k in range(j, len(v2))])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    j -= 1\n",
    "\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "        return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, x: float, n: int) -> float:\n",
    "        if n == 0: return 1\n",
    "        sign = (n >= 0)\n",
    "        if not sign: n = -n\n",
    "        \n",
    "        odd = []\n",
    "        while n > 1:\n",
    "            odd.append(n % 2)\n",
    "            n = n // 2\n",
    "        \n",
    "        s = x\n",
    "        for i in reversed(odd):\n",
    "            if i: s = s * s * x\n",
    "            else: s = s * s\n",
    "        \n",
    "        if sign: return s\n",
    "        else: return 1/s \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:\n",
    "        mp = {}\n",
    "        for x, y in reversed(operations):\n",
    "            mp[x] = mp.get(y, y)\n",
    "        return [mp.get(num, num) for num in nums]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:\n",
    "        res = {}\n",
    "        for i, j in reversed(operations):\n",
    "            res[i] = res.get(j, j)\n",
    "        nums = [res.get(i, i) for i in nums]\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:\n",
    "        mp = {}\n",
    "        for x, y in reversed(operations):\n",
    "            mp[x] = mp.get(y, y)\n",
    "        return [mp.get(num, num) for num in nums]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:\n",
    "        mp = {}\n",
    "        for x, y in reversed(operations):\n",
    "            mp[x] = mp.get(y, y)\n",
    "        return [mp.get(num, num) for num in nums]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:\n",
    "        mp = {}\n",
    "        for x, y in reversed(operations):\n",
    "            mp[x] = mp.get(y, y)\n",
    "        return [mp.get(num, num) for num in nums]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 array: arr\n",
    "        把所有元素換成\"他右邊最大\"的那個(不包含自己), 最後一個元素是 -1\n",
    "        \"\"\"\n",
    "\n",
    "        # 暴力法會超時: O(n^2)\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            max_value = -1\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                max_value = max(max_value, arr[j])\n",
    "            result[i] = max_value\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 max 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = max(arr[i+1:])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 sort 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = sorted(arr[i+1:])[-1]\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 往回頭比\n",
    "        # 沒想過有這種寫法... 太強了\n",
    "        \"\"\"\n",
    "        1. 題目要求的是 \"除了自己\" 的右邊, 找最大值\n",
    "        2. 對於 arr 最後一個元素: arr[-1] 而言, 它一定會被換成 -1\n",
    "           所以我們從 arr[-2] 開始看起\n",
    "\n",
    "            a. result[-1] 一定是 -1\n",
    "            b. result[-2] 一定是 arr[-1] 和 \"-1\" 做比較, 找出最大值\n",
    "               result[-2] = max(result[-1], arr[-1])\n",
    "\n",
    "            c. result[-3] = max(result[-2], arr[-2])\n",
    "            由於已經找出了 result[-2]: 範圍的最大值(包含 result[-2:-1])\n",
    "            再往前面走一格, 拿 arr[-2] 和 result[-2] 比誰是最大值 \n",
    "            在這個狀況下只要比兩個數字就好了\n",
    "        \"\"\"\n",
    "\n",
    "        # 聽了 neetcode 前半段的寫法\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr) - 2, -1, -1):\n",
    "            result[i] = max(result[i + 1], arr[i + 1])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 這樣寫也可以，結果會出錯\n",
    "        \"\"\"\n",
    "        result = [-1]\n",
    "        for n in reversed(arr[1:]):\n",
    "            result.append(max(result[-1], n))\n",
    "        return reversed(result)\n",
    "        \"\"\"\n",
    "\n",
    "        # neetcode 的解法:\n",
    "        # mem: O(1)\n",
    "        old_max = -1\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            new_max = max(old_max, arr[i])\n",
    "            arr[i]  = old_max\n",
    "            old_max = new_max\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        left_max = arr[:]\n",
    "        left_max[-1] = -1\n",
    "        temp_max = arr[-1]\n",
    "        for i in reversed(range(len(arr) - 1)):\n",
    "            left_max[i] = temp_max\n",
    "            temp_max = max(temp_max, arr[i])\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            arr[i] = left_max[i]\n",
    "\n",
    "        # arr[-1] = -1\n",
    "\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        \"\"\"\n",
    "        給一個 array: arr\n",
    "        把所有元素換成\"他右邊最大\"的那個(不包含自己), 最後一個元素是 -1\n",
    "        \"\"\"\n",
    "\n",
    "        # 暴力法會超時: O(n^2)\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            max_value = -1\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                max_value = max(max_value, arr[j])\n",
    "            result[i] = max_value\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 max 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = max(arr[i+1:])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 使用 sort 也會超時\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if i + 1 < len(arr):\n",
    "                result[i] = sorted(arr[i+1:])[-1]\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 往回頭比\n",
    "        # 沒想過有這種寫法... 太強了\n",
    "        \"\"\"\n",
    "        1. 題目要求的是 \"除了自己\" 的右邊, 找最大值\n",
    "        2. 對於 arr 最後一個元素: arr[-1] 而言, 它一定會被換成 -1\n",
    "           所以我們從 arr[-2] 開始看起\n",
    "\n",
    "            a. result[-1] 一定是 -1\n",
    "            b. result[-2] 一定是 arr[-1] 和 \"-1\" 做比較, 找出最大值\n",
    "               result[-2] = max(result[-1], arr[-1])\n",
    "\n",
    "            c. result[-3] = max(result[-2], arr[-2])\n",
    "            由於已經找出了 result[-2]: 範圍的最大值(包含 result[-2:-1])\n",
    "            再往前面走一格, 拿 arr[-2] 和 result[-2] 比誰是最大值 \n",
    "            在這個狀況下只要比兩個數字就好了\n",
    "        \"\"\"\n",
    "\n",
    "        # 聽了 neetcode 前半段的寫法: mem: O(n)\n",
    "        \"\"\"\n",
    "        result = [-1] * len(arr)\n",
    "        for i in range(len(arr) - 2, -1, -1):\n",
    "            result[i] = max(result[i + 1], arr[i + 1])\n",
    "        return result\n",
    "        \"\"\"\n",
    "\n",
    "        # 這樣寫也可以，但結果會報錯\n",
    "        \"\"\"\n",
    "        result = [-1]\n",
    "        for n in reversed(arr[1:]):\n",
    "            result.append(max(result[-1], n))\n",
    "        return reversed(result)\n",
    "        \"\"\"\n",
    "\n",
    "        # neetcode 的解法: mem: O(1)\n",
    "        old_max = -1\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            new_max = max(old_max, arr[i])\n",
    "            arr[i]  = old_max\n",
    "            old_max = new_max\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        mx=-1\n",
    "        for x in reversed(arr):\n",
    "            res.append(mx)\n",
    "            mx=max(mx,x)\n",
    "        res.reverse()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        res = [-1]\n",
    "        max_value = arr[-1]\n",
    "        for ii in range(len(arr) - 1, 0, -1):\n",
    "            max_value = max(max_value, arr[ii])\n",
    "            res.append(max_value)\n",
    "        \n",
    "        print(res)\n",
    "        res.reverse()\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceElements(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        if n == 1:\n",
    "            return [-1]\n",
    "\n",
    "        res = [-1]\n",
    "        maxV = arr[-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            res.append(maxV)\n",
    "            if arr[i]>maxV:\n",
    "                maxV = arr[i]\n",
    "        res.reverse()\n",
    "        return res\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replaceWords(self, dictionary: List[str], sentence: str) -> str:\n",
    "        dictionary.sort(reverse=True)\n",
    "        trie = {}\n",
    "        for word in dictionary:\n",
    "            cur = trie\n",
    "            for i in range(len(word)):\n",
    "                if word[i] in cur:\n",
    "                    if i==len(word)-1:\n",
    "                        cur[word[i]] = {}\n",
    "                        break\n",
    "                    cur = cur[word[i]]\n",
    "                else:\n",
    "                    cur[word[i]] = {}\n",
    "                    cur = cur[word[i]]\n",
    "        res = \"\"\n",
    "        for word in sentence.split(\" \"):\n",
    "            cur = trie\n",
    "            new_word = \"\"\n",
    "            for w in word:\n",
    "                if w in cur:\n",
    "                    new_word = new_word+w\n",
    "                else:\n",
    "                    break\n",
    "                cur = cur[w]\n",
    "            if len(cur)==0:\n",
    "                res = res + new_word + \" \"\n",
    "            else:\n",
    "                res = res + word + \" \"\n",
    "        return res[:-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        hashmap = {}\n",
    "        for pair in adjacentPairs:\n",
    "            x, y = pair\n",
    "            if x in hashmap and y in hashmap:\n",
    "                qx = hashmap.pop(x)\n",
    "                qy = hashmap.pop(y)\n",
    "                if qx[0] == x and qy[0] == y:\n",
    "                    hashmap.pop(qx[-1])\n",
    "                    hashmap.pop(qy[-1])\n",
    "                    qx.reverse()\n",
    "                    qx.extend(qy)\n",
    "                    hashmap[qx[0]] = qx\n",
    "                    hashmap[qx[-1]] = qx\n",
    "                elif qx[0] == x and qy[-1] == y:\n",
    "                    hashmap.pop(qx[-1])\n",
    "                    hashmap.pop(qy[0])\n",
    "                    qy.extend(qx)\n",
    "                    hashmap[qy[0]] = qy\n",
    "                    hashmap[qy[-1]] = qy\n",
    "                elif qx[-1] == x and qy[0] == y:\n",
    "                    hashmap.pop(qx[0])\n",
    "                    hashmap.pop(qy[-1])\n",
    "                    qx.extend(qy)\n",
    "                    hashmap[qx[0]] = qx\n",
    "                    hashmap[qx[-1]] = qx\n",
    "                elif qx[-1] == x and qy[-1] == y:\n",
    "                    hashmap.pop(qx[0])\n",
    "                    hashmap.pop(qy[0])\n",
    "                    qy.reverse()\n",
    "                    qx.extend(qy)\n",
    "                    hashmap[qx[0]] = qx\n",
    "                    hashmap[qx[-1]] = qx\n",
    "            elif x in hashmap:\n",
    "                q = hashmap.pop(x)\n",
    "                if q[0] == x:\n",
    "                    q.appendleft(y)\n",
    "                elif q[-1] == x:\n",
    "                    q.append(y)\n",
    "                hashmap[y] = q\n",
    "            elif y in hashmap:\n",
    "                q = hashmap.pop(y)\n",
    "                if q[0] == y:\n",
    "                    q.appendleft(x)\n",
    "                elif q[-1] == y:\n",
    "                    q.append(x)\n",
    "                hashmap[x] = q\n",
    "            else:\n",
    "                q = deque([x, y])\n",
    "                hashmap[x] = q\n",
    "                hashmap[y] = q\n",
    "\n",
    "        return list(list(hashmap.values())[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnDirectedEulerPath:\n",
    "    def __init__(self, n, pairs):\n",
    "        # 数组形式存储的有向连接关系\n",
    "        self.n = n\n",
    "        self.pairs = pairs\n",
    "        # 欧拉路径上的每条边和经过的几点\n",
    "        self.paths = list()\n",
    "        self.nodes = list()\n",
    "        self.exist = False\n",
    "        self.get_euler_path()\n",
    "        return\n",
    "\n",
    "    def get_euler_path(self):\n",
    "        # 存顶点的出入度\n",
    "        degree = [0]*self.n\n",
    "        # 存储图关系\n",
    "        edge = [defaultdict(int) for _ in range(self.n)]\n",
    "        for i, j in self.pairs:\n",
    "            degree[i] += 1\n",
    "            degree[j] += 1\n",
    "            edge[i][j] += 1\n",
    "            edge[j][i] += 1\n",
    "\n",
    "        # 寻找起始节点\n",
    "        starts = []\n",
    "        zero = 0\n",
    "        for i in range(self.n):\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始\n",
    "            if degree[i] % 2:\n",
    "                starts.append(i)\n",
    "            else:\n",
    "                zero += 1\n",
    "        del degree\n",
    "\n",
    "        # 不存在欧拉路径\n",
    "        if not len(starts) == 2:\n",
    "            if zero != self.n:\n",
    "                return\n",
    "            starts = [0]\n",
    "\n",
    "        \"\"\"\n",
    "        改进前的深搜版本\n",
    "        def dfs(pre):\n",
    "            # 使用深度优先搜索（Hierholzer算法）求解欧拉通路\n",
    "            for nex in range(self.n):\n",
    "                while edge[pre][nex]:\n",
    "                    edge[pre][nex] -= 1\n",
    "                    edge[nex][pre] -= 1\n",
    "                    dfs(nex)\n",
    "                    self.nodes.append(nex)\n",
    "                    self.paths.append([pre, nex])\n",
    "            return\n",
    "\n",
    "        dfs(starts[0])\n",
    "        self.paths.reverse()\n",
    "        self.nodes.append(starts[0])\n",
    "        self.nodes.reverse()\n",
    "        \"\"\"\n",
    "        # 使用迭代版本Hierholzer算法计算\n",
    "        stack = [starts[0]]\n",
    "        while stack:\n",
    "            current = stack[-1]\n",
    "            next_node = None\n",
    "            for nex in edge[current]:\n",
    "                if edge[current][nex]:\n",
    "                    edge[current][nex] -= 1\n",
    "                    edge[nex][current] -= 1\n",
    "                    next_node = nex\n",
    "                    stack.append(next_node)\n",
    "                    break\n",
    "            if next_node is None:\n",
    "                self.nodes.append(current)\n",
    "                if len(stack) > 1:\n",
    "                    pre = stack[-2]\n",
    "                    self.paths.append([pre, current])\n",
    "                stack.pop()\n",
    "        self.paths.reverse()\n",
    "        self.nodes.reverse()\n",
    "        # 注意判断所有边都经过的才算欧拉路径\n",
    "        if len(self.nodes) == len(self.pairs) + 1:\n",
    "            self.exist = True\n",
    "        return\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        nodes= set()\n",
    "\n",
    "        for a, b in adjacentPairs:\n",
    "            nodes.add(a)\n",
    "            nodes.add(b)\n",
    "        nodes = sorted(nodes)\n",
    "        ind = {num: i for i, num in enumerate(nodes)}\n",
    "        pairs = [[ind[x], ind[y]] for x, y in adjacentPairs]\n",
    "        n = len(nodes)\n",
    "        ruler = UnDirectedEulerPath(n, pairs)\n",
    "        return [nodes[x] for x in ruler.nodes]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        pairs=adjacentPairs\n",
    "        next_dic={}\n",
    "        #next_dic=defaultdict(list)\n",
    "\n",
    "        for p in pairs:\n",
    "            next_dic[p[0]]=next_dic.get(p[0],[])+[p[1]]\n",
    "            next_dic[p[1]]=next_dic.get(p[1],[])+[p[0]]\n",
    " \n",
    "        #print(next_dic)\n",
    "\n",
    "        def get_next(val):\n",
    "            nexts=next_dic[val]\n",
    "            if len(nexts)==0:\n",
    "                return None\n",
    "            next_dic[nexts[0]].remove(val)\n",
    "            next=nexts[0]\n",
    "            del next_dic[val][0]\n",
    "            return next\n",
    "            \n",
    "\n",
    "        def merge_nums(cur,cur_nums):\n",
    "            next=get_next(cur)\n",
    "            \n",
    "            #print(cur,next,next_dic)\n",
    "            if next is None:\n",
    "                return\n",
    "            else:\n",
    "                cur_nums.append(next)\n",
    "                merge_nums(next,cur_nums)\n",
    "\n",
    "        start=pairs[0][0]\n",
    "        nums1=[]\n",
    "        merge_nums(start,nums1)\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        nums2=[]\n",
    "        merge_nums(start, nums2)\n",
    "        nums1.reverse()\n",
    "        return nums1+[start]+nums2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        pairs=adjacentPairs\n",
    "        next_dic=defaultdict(list)\n",
    "\n",
    "        for p in pairs:\n",
    "            next_dic[p[0]].append(p[1])\n",
    "            next_dic[p[1]].append(p[0])\n",
    " \n",
    "        #print(next_dic)\n",
    "\n",
    "        def get_next(val):\n",
    "            nexts=next_dic[val]\n",
    "            if len(nexts)==0:\n",
    "                return None\n",
    "            next_dic[nexts[0]].remove(val)\n",
    "            next=nexts[0]\n",
    "            del next_dic[val][0]\n",
    "            return next\n",
    "            \n",
    "\n",
    "        def merge_nums(cur,cur_nums):\n",
    "            next=get_next(cur)\n",
    "            \n",
    "            #print(cur,next,next_dic)\n",
    "            if next is None:\n",
    "                return\n",
    "            else:\n",
    "                cur_nums.append(next)\n",
    "                merge_nums(next,cur_nums)\n",
    "\n",
    "        start=pairs[0][0]\n",
    "        nums1=[]\n",
    "        merge_nums(start,nums1)\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        nums2=[]\n",
    "        merge_nums(start, nums2)\n",
    "        nums1.reverse()\n",
    "        return nums1+[start]+nums2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        pairs=adjacentPairs\n",
    "        next_dic={}\n",
    "\n",
    "        for p in pairs:\n",
    "            try:\n",
    "                next_dic[p[0]].append(p[1])\n",
    "            except:\n",
    "                next_dic[p[0]]=[p[1]]\n",
    "            try:\n",
    "                next_dic[p[1]].append(p[0])\n",
    "            except:\n",
    "                next_dic[p[1]]=[p[0]]\n",
    "\n",
    "        #print(next_dic)\n",
    "\n",
    "        def get_next(val):\n",
    "            nexts=next_dic[val]\n",
    "            if len(nexts)==0:\n",
    "                return None\n",
    "            next_dic[nexts[0]].remove(val)\n",
    "            next=nexts[0]\n",
    "            del next_dic[val][0]\n",
    "            return next\n",
    "            \n",
    "\n",
    "        def merge_nums(cur,cur_nums):\n",
    "            next=get_next(cur)\n",
    "            \n",
    "            #print(cur,next,next_dic)\n",
    "            if next is None:\n",
    "                return\n",
    "            else:\n",
    "                cur_nums.append(next)\n",
    "                merge_nums(next,cur_nums)\n",
    "\n",
    "        start=pairs[0][0]\n",
    "        nums1=[]\n",
    "        merge_nums(start,nums1)\n",
    "        \n",
    "        start = pairs[0][0]\n",
    "        nums2=[]\n",
    "        merge_nums(start, nums2)\n",
    "        nums1.reverse()\n",
    "        return nums1+[start]+nums2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        adj = defaultdict(list)\n",
    "        start = None\n",
    "        for a, b in adjacentPairs:\n",
    "            adj[a].append(b)\n",
    "            adj[b].append(a)\n",
    "            if start is None:\n",
    "                start = a\n",
    "        visited = defaultdict(bool)\n",
    "        ans = []\n",
    "        def dfs(s, i, reverse=False):\n",
    "            visited[i] = True\n",
    "            if reverse:\n",
    "                ans.append(i)\n",
    "                for j in adj[i]:\n",
    "                    if not visited[j] and j != s:\n",
    "                        dfs(s, j, True)\n",
    "            else:\n",
    "                for j in adj[i]:\n",
    "                    if not visited[j] and j != s:\n",
    "                        dfs(s, j)\n",
    "                ans.append(i)\n",
    "        if len(adj[start]) == 2:\n",
    "            dfs(start, adj[start][0])\n",
    "            ans.append(start)\n",
    "            dfs(start, adj[start][1], True)\n",
    "        else:\n",
    "            ans.append(start)\n",
    "            dfs(start, adj[start][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        class Node:\n",
    "            def __init__(self, x):\n",
    "                self.val = x\n",
    "                self.left = None\n",
    "                self.right = None\n",
    "\n",
    "            def reverse(self, rtype=\"both\"):\n",
    "                left = self.left\n",
    "                right = self.right\n",
    "                if rtype != 'left' and right:\n",
    "                    right.reverse('right')\n",
    "                if rtype != 'right' and left:\n",
    "                    left.reverse('left')\n",
    "                self.left, self.right = right, left\n",
    "\n",
    "        n = len(adjacentPairs) + 1\n",
    "        nodes = {}\n",
    "        for u, v in adjacentPairs:\n",
    "            if u not in nodes:\n",
    "                nodes[u] = Node(u)\n",
    "            if v not in nodes:\n",
    "                nodes[v] = Node(v)\n",
    "            if not nodes[u].right:\n",
    "                if nodes[v].left:\n",
    "                    nodes[v].reverse()\n",
    "                nodes[u].right = nodes[v]\n",
    "                nodes[v].left = nodes[u]\n",
    "            else:\n",
    "                if nodes[v].right:\n",
    "                    nodes[v].reverse()\n",
    "                nodes[u].left = nodes[v]\n",
    "                nodes[v].right = nodes[u]\n",
    "\n",
    "        res = []\n",
    "        visited = set()\n",
    "        for num in nodes:\n",
    "            if num not in visited:\n",
    "                node = nodes[num]\n",
    "                while node.left:\n",
    "                    node = node.left\n",
    "                while node:\n",
    "                    res.append(node.val)\n",
    "                    visited.add(node.val)\n",
    "                    node = node.right\n",
    "        return res\n",
    "        \n",
    "        # par, rank = list(range(n)), [0]*n\n",
    "\n",
    "        # def find(x):\n",
    "        #     if par[x] != x:\n",
    "        #         par[x] = find(par[x])\n",
    "        #     reutrn par[x]\n",
    "\n",
    "        # def unite(x, y):\n",
    "        #     x = find(x)\n",
    "        #     y = find(y)\n",
    "        #     if rank[x] < rank[y]:\n",
    "        #         par[x] = par[y]\n",
    "        #     else:\n",
    "        #         par[y] = par[x]\n",
    "        #         rank[x] += 1\n",
    "        \n",
    "        # def isSame(x, y):\n",
    "        #     return find(x) == find(y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnDirectedEulerPath:\n",
    "    def __init__(self, n, pairs):\n",
    "        # 数组形式存储的有向连接关系\n",
    "        self.n = n\n",
    "        self.pairs = pairs\n",
    "        # 欧拉路径上的每条边和经过的几点\n",
    "        self.paths = list()\n",
    "        self.nodes = list()\n",
    "        self.exist = False\n",
    "        self.get_euler_path()\n",
    "        return\n",
    "\n",
    "    def get_euler_path(self):\n",
    "        # 存顶点的出入度\n",
    "        degree = [0]*self.n\n",
    "        # 存储图关系\n",
    "        edge = [dict() for _ in range(self.n)]\n",
    "        for i, j in self.pairs:\n",
    "            degree[i] += 1\n",
    "            degree[j] += 1\n",
    "            edge[i][j] = edge[i].get(j, 0) + 1\n",
    "            edge[j][i] = edge[j].get(i, 0) + 1\n",
    "        edge_dct = [deque(sorted(dt)) for dt in edge]  # 从小到大进行序号遍历\n",
    "        # 寻找起始节点\n",
    "        starts = []\n",
    "        zero = 0\n",
    "        for i in range(self.n):\n",
    "            # 如果有节点出度比入度恰好多 1，那么只有它才能是起始\n",
    "            if degree[i] % 2:\n",
    "                starts.append(i)\n",
    "            else:\n",
    "                zero += 1\n",
    "        del degree\n",
    "\n",
    "        # 不存在欧拉路径\n",
    "        if not len(starts) == 2:\n",
    "            if zero != self.n:\n",
    "                return\n",
    "            starts = [0]\n",
    "\n",
    "        # 使用迭代版本Hierholzer算法计算\n",
    "        stack = [starts[0]]\n",
    "        while stack:\n",
    "            current = stack[-1]\n",
    "            next_node = None\n",
    "            while edge_dct[current]:\n",
    "                if not edge[current][edge_dct[current][0]]:\n",
    "                    edge_dct[current].popleft()\n",
    "                    continue\n",
    "                nex = edge_dct[current][0]\n",
    "                if edge[current][nex]:\n",
    "                    edge[current][nex] -= 1\n",
    "                    edge[nex][current] -= 1\n",
    "                    next_node = nex\n",
    "                    stack.append(next_node)\n",
    "                    break\n",
    "            if next_node is None:\n",
    "                self.nodes.append(current)\n",
    "                if len(stack) > 1:\n",
    "                    pre = stack[-2]\n",
    "                    self.paths.append([pre, current])\n",
    "                stack.pop()\n",
    "        self.paths.reverse()\n",
    "        self.nodes.reverse()\n",
    "        # 注意判断所有边都经过的才算欧拉路径\n",
    "        if len(self.nodes) == len(self.pairs) + 1:\n",
    "            self.exist = True\n",
    "        return\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:\n",
    "        nodes= set()\n",
    "\n",
    "        for a, b in adjacentPairs:\n",
    "            nodes.add(a)\n",
    "            nodes.add(b)\n",
    "        nodes = sorted(nodes)\n",
    "        ind = {num: i for i, num in enumerate(nodes)}\n",
    "        pairs = [[ind[x], ind[y]] for x, y in adjacentPairs]\n",
    "        n = len(nodes)\n",
    "        ruler = UnDirectedEulerPath(n, pairs)\n",
    "        return [nodes[x] for x in ruler.nodes]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "      deck.sort(reverse=True)\n",
    "      ans = [deck[0]]\n",
    "      i = 1\n",
    "      while len(ans) < len(deck):\n",
    "        ans = [ans[-1]] + ans\n",
    "        ans.pop()\n",
    "        ans = [deck[i]] + ans\n",
    "        i += 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort(reverse = True)\n",
    "        stack = collections.deque()\n",
    "        for val in deck:\n",
    "            if not stack: stack.append(val)\n",
    "            else:\n",
    "                stack.appendleft(stack.pop())\n",
    "                stack.appendleft(val)\n",
    "        return [x for x in stack]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "      deck.sort(reverse=True)\n",
    "      ans = [deck[0]]\n",
    "      i = 1\n",
    "      while len(ans) < len(deck):\n",
    "        ans = [ans[-1]] + ans\n",
    "        ans.pop()\n",
    "        ans = [deck[i]] + ans\n",
    "        i += 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort()\n",
    "        s_sort = deck\n",
    "        s_result = []\n",
    "        while len(s_sort)>0:\n",
    "\n",
    "            s_result.append(s_sort[-1])\n",
    "            s_sort.pop()\n",
    "            s_result.insert(-1,s_result[0])\n",
    "            s_result.pop(0)\n",
    "        \n",
    "        s_result.reverse()\n",
    "\n",
    "        return s_result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort(reverse = True)\n",
    "        stack = collections.deque()\n",
    "        for val in deck:\n",
    "            if not stack: stack.append(val)\n",
    "            else:\n",
    "                stack.appendleft(stack.pop())\n",
    "                stack.appendleft(val)\n",
    "        return [x for x in stack]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort()\n",
    "        s_sort = deck\n",
    "        s_result = []\n",
    "        while len(s_sort)>0:\n",
    "\n",
    "            s_result.append(s_sort[-1])\n",
    "            s_sort.pop()\n",
    "            s_result.insert(-1,s_result[0])\n",
    "            s_result.pop(0)\n",
    "        \n",
    "        s_result.reverse()\n",
    "\n",
    "        return s_result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort(reverse=True)\n",
    "        ans = deque([deck[0]])\n",
    "        for i in range(1, len(deck)):\n",
    "            if ans:\n",
    "                front = ans.popleft()\n",
    "                ans.append(front)\n",
    "            ans.append(deck[i])\n",
    "        ans.reverse()\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort(reverse=True)\n",
    "        from collections import deque\n",
    "        q=deque()\n",
    "        # print(deck)\n",
    "        for x in deck:\n",
    "            q.rotate()\n",
    "            q.appendleft(x)\n",
    "            # print(q)\n",
    "        return list(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort(reverse=True)\n",
    "        ans=[]\n",
    "        def move_right(nums):\n",
    "            if not nums:\n",
    "                return nums\n",
    "            temp=nums[-1]\n",
    "            for i in range(len(nums)-1,0,-1):\n",
    "                nums[i]=nums[i-1]\n",
    "            nums[0]=temp\n",
    "            return nums\n",
    "        for i,num in enumerate(deck):\n",
    "            ans=move_right(ans)\n",
    "            ans.insert(0,num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort(reverse=True)\n",
    "\n",
    "        dq = deque()\n",
    "        for card in deck:\n",
    "            if dq:\n",
    "                dq.appendleft(dq.pop())\n",
    "            dq.appendleft(card)\n",
    "        \n",
    "        return list(dq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def deckRevealedIncreasing(self, deck):\n",
    "        deck.sort(reverse=True)\n",
    "        ret = collections.deque()\n",
    "        for i in range(len(deck)):\n",
    "            if ret:\n",
    "                x = ret.pop()\n",
    "                ret.extendleft([x, deck[i]])\n",
    "            else:\n",
    "                ret.append(deck[i])\n",
    "        return list(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        # deck.sort(reverse=True)\n",
    "        # from collections import deque\n",
    "        # q=deque()\n",
    "        # # print(deck)\n",
    "        # for x in deck:\n",
    "        #     q.rotate()\n",
    "        #     q.appendleft(x)\n",
    "        #     # print(q)\n",
    "        # return list(q)\n",
    "\n",
    "\n",
    "\n",
    "        deck.sort()\n",
    "        ret = [0] * len(deck)\n",
    "        index = deque(range(len(deck)))\n",
    "        for i in sorted(deck):\n",
    "            ret[index.popleft()] = i\n",
    "            if index:\n",
    "                index.append(index.popleft())\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        n = len(deck)\n",
    "        index = list(range(n))\n",
    "        res = [0] * n\n",
    "\n",
    "        for card in sorted(deck):\n",
    "            res[index.pop(0)] = card\n",
    "\n",
    "            if index:\n",
    "                index.append(index.pop(0))\n",
    "        return res\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "#         check = sorted(deck, reverse=True)\n",
    "#         # print(check)\n",
    "#         newCheck = []\n",
    "#         while check:\n",
    "#             i = check.pop(0)\n",
    "#             # print(i)\n",
    "#             newCheck.insert(0, i)\n",
    "#             if check and len(newCheck) > 1:\n",
    "#                 j = newCheck.pop()\n",
    "#                 newCheck.insert(0, j)\n",
    "#         return newCheck\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        res:List = []\n",
    "        deck.sort()\n",
    "        for i in reversed(range(len(deck))):\n",
    "            if len(res) == 0:\n",
    "                res.append(deck[i])\n",
    "                continue\n",
    "            last = res.pop()\n",
    "            res.insert(0,last)\n",
    "            res.insert(0,deck[i])\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort()\n",
    "        res:List = []\n",
    "        for i in reversed(range(len(deck))):\n",
    "            if len(res) == 0:\n",
    "                res.append(deck[i])\n",
    "                continue\n",
    "            res.insert(0,res.pop())\n",
    "            res.insert(0,deck[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        deck.sort(reverse = True)\n",
    "        q = queue.deque()\n",
    "        for i in range(len(deck)):\n",
    "            if not q: q.append(deck[i])\n",
    "            else:\n",
    "                q.appendleft(q.pop())\n",
    "                q.appendleft(deck[i])\n",
    "        return list(q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:\n",
    "        res = self.digui(deck, 1)\n",
    "        # if len(res) % 2 == 1:\n",
    "        #     res_out = res[1:]\n",
    "        #     res_out.append(res[0])\n",
    "        # else:\n",
    "        #     res_out = res\n",
    "        return res\n",
    "    \n",
    "    def digui(self, nums, jiou):\n",
    "        print(nums)\n",
    "        if len(nums) == 1:\n",
    "            return nums\n",
    "        if len(nums)  == 2:\n",
    "            if jiou:\n",
    "                nums.sort()\n",
    "                return nums\n",
    "            else:\n",
    "                nums.sort(reverse = True)\n",
    "                return nums\n",
    "        nums.sort()\n",
    "        ou = nums[:ceil(len(nums) / 2)]\n",
    "        ji = self.digui(nums[ceil(len(nums) / 2):], len(nums) % 2 == 0)\n",
    "        i = 0\n",
    "        res = []\n",
    "        while i < len(ou):\n",
    "            res.append(ou[i])\n",
    "            if i < len(ji):\n",
    "                res.append(ji[i])\n",
    "            i += 1\n",
    "        if not jiou:\n",
    "            res_out = [res[-1]]\n",
    "            res_out.extend(res[:-1])\n",
    "        else:\n",
    "            res_out = res\n",
    "        return res_out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        cnt = 0\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if num&1:\n",
    "                cur += 1\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt = cur + 1\n",
    "                cur = 0\n",
    "            num = num>>1\n",
    "            res = max(res, cnt)\n",
    "                \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0  # 当前位置为止连续1的个数\n",
    "        insert=0  # 在当前位置变成1，往前数连续1的最大个数\n",
    "        res=1  # 保存insert最大值即可\n",
    "        for i in range(32):\n",
    "            if num&(1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num >= 0:\n",
    "            bnum = bin(num)[2:]\n",
    "        else:\n",
    "            bnum = bin(num & 0xffffffff)[2:]\n",
    "        if len(bnum) < 32:\n",
    "            bnum = \"0\" + bnum\n",
    "        left_index = 0\n",
    "        right_index = 0\n",
    "        ans = 0\n",
    "        zero_indexes = list()\n",
    "        while right_index < len(bnum):\n",
    "            if bnum[right_index] == '0':\n",
    "                zero_indexes.append(right_index)\n",
    "            if len(zero_indexes) > 1:\n",
    "                ans = max(ans, right_index - left_index)\n",
    "                left_index = zero_indexes.pop(0) + 1\n",
    "            right_index += 1\n",
    "            if right_index == len(bnum):\n",
    "                ans = max(ans, right_index - left_index)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # 思路: 目标长串中只能包含一个0 \n",
    "        # 从低位到高度遍历\n",
    "        #   遇到1, 则当前连续1长串长度 +1\n",
    "        #   遇到0, 则当前连续1长度长度 = 当前索引 - 上次遇到0的索引\n",
    "\n",
    "        #   8   4     \n",
    "        # 11011101111\n",
    "\n",
    "        cur = 0\n",
    "        rs = 0\n",
    "        last0 = -1  # 上次遇到0的位置\n",
    "        for i in range(32):\n",
    "            # 判断第i位是否为1\n",
    "            if num & (1 << i) != 0:\n",
    "                # 如果为1, 当前连续1的个数++\n",
    "                cur += 1\n",
    "            else:\n",
    "                rs = max(rs, cur)\n",
    "                # 如果为0\n",
    "                cur = i - last0\n",
    "                last0 = i\n",
    "        rs = max(rs, cur)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # print(num)\n",
    "        # print(bin(num))\n",
    "        num=bin(num & 0xffffffff)[2:]\n",
    "        # print(num)\n",
    "\n",
    "        num=\"0\"*(32-len(num))+num\n",
    "        index=0\n",
    "        maxlen=0\n",
    "\n",
    "        while index<len(num):\n",
    "            nowlen=0\n",
    "\n",
    "            if num[index]==\"1\":\n",
    "                while index<len(num) and num[index]==\"1\":\n",
    "                    nowlen+=1\n",
    "                    index+=1\n",
    "\n",
    "                if index<len(num):\n",
    "                    last=index+1\n",
    "                    nowlen+=1\n",
    "                    index+=1\n",
    "                    while index<len(num) and num[index]==\"1\":\n",
    "                        nowlen+=1\n",
    "                        index+=1\n",
    "                    index=last\n",
    "\n",
    "            else:\n",
    "                nowlen+=1\n",
    "                index+=1\n",
    "                last=index\n",
    "                while index<len(num) and num[index]==\"1\":\n",
    "                    nowlen+=1\n",
    "                    index+=1\n",
    "                index=last\n",
    "\n",
    "            maxlen=max(maxlen,nowlen)\n",
    "            \n",
    "\n",
    "        return maxlen\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        length = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                length += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = length + 1\n",
    "                length = 0\n",
    "            \n",
    "            res = max(res, insert)\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num += 2**32\n",
    "        bits = []\n",
    "        temp = num\n",
    "        while temp != 0:\n",
    "            bits.append(temp % 2)\n",
    "            temp //= 2\n",
    "        print(bin(num))\n",
    "        max1 = 1\n",
    "        prev1, current1, num0 = 0, 0, 0\n",
    "        for i in range(len(bits)):\n",
    "            if bits[i] == 1:\n",
    "                current1 += 1\n",
    "                temp_len = current1 + 1\n",
    "                if num0 <= 1:\n",
    "                    temp_len += prev1\n",
    "                max1 = max(max1, temp_len)\n",
    "            elif i > 0 and bits[i - 1] == 1:\n",
    "                num0 = 1\n",
    "                prev1 = current1\n",
    "                current1 = 0\n",
    "            else:\n",
    "                num0 += 1\n",
    "        return min(32, max1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        left = 0\n",
    "        counter = 0 \n",
    "        res = 0\n",
    "        for right in range(0 ,32): \n",
    "            counter += num >> right & 1 ^ 1\n",
    "            while counter > 1:\n",
    "                counter -= num >> left & 1 ^ 1\n",
    "                left += 1\n",
    "            res = max(right-left+1, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # 思路: 目标长串中只能包含一个0 \n",
    "        # 从低位到高度遍历\n",
    "        #   遇到1, 则当前连续1长串长度 +1\n",
    "        #   遇到0, 则当前连续1长度长度 = 当前索引 - 上次遇到0的索引\n",
    "\n",
    "        #   8   4     \n",
    "        # 11011101111\n",
    "\n",
    "        cur = 0\n",
    "        rs = 0\n",
    "        last0 = -1  # 上次遇到0的位置\n",
    "        for i in range(32):\n",
    "            # 判断第i位是否为1\n",
    "            if num & (1 << i) != 0:\n",
    "                # 如果为1, 当前连续1的个数++\n",
    "                cur += 1\n",
    "            else:\n",
    "                # 如果为0\n",
    "                cur = i - last0\n",
    "                last0 = i\n",
    "            rs = max(rs, cur)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        c=r=max1=0\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                c+=1\n",
    "                r+=1\n",
    "            else:\n",
    "                r=c+1\n",
    "                c=0\n",
    "            max1=max(max1,r)\n",
    "        return max1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num<0:\n",
    "            num=int(num+math.pow(2,32))\n",
    "        w= list(bin(num)[2:])\n",
    "        t=[0]\n",
    "        for i in range(len(w)):\n",
    "            if  ascii('0')<= ascii(w[i])<=ascii('9'):\n",
    "                t.append(int(w[i]))\n",
    "        r=[0 for i in range(len(t))]\n",
    "        temp=[0 for i in range(len(t))]\n",
    "        temp[0]=1\n",
    "        r[0]=0\n",
    "        q=0\n",
    "        for i in range(1,len(t)):\n",
    "            if  t[i]==0:\n",
    "                j=i-1\n",
    "                while  True:\n",
    "                    if t[j]==0 or j==0:\n",
    "                        break\n",
    "                    j=j-1\n",
    "                temp[i]=i-j\n",
    "            else:\n",
    "                temp[i]=temp[i-1]+1\n",
    "            r[i]=max(temp[i],r[i-1])\n",
    "            if r[i]>q:\n",
    "                q=r[i]\n",
    "        if q>32:\n",
    "            q=32\n",
    "        return q\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 2**31 + 2**31 + num\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 2**32 - 1:\n",
    "            return 32\n",
    "        bits = []\n",
    "        zeros = [0]\n",
    "        while True:\n",
    "            bits.append(num % 2)\n",
    "            if bits[-1] == 0:\n",
    "                zeros.append(len(bits))\n",
    "            num = num // 2\n",
    "            if num == 0:\n",
    "                break\n",
    "        zeros.append(len(bits)+1)\n",
    "\n",
    "        # print(bits)\n",
    "        if len(zeros) == 2:\n",
    "            return zeros[1] - zeros[0]\n",
    "        # print(zeros)\n",
    "        maxnum = zeros[2] - zeros[0] - 1\n",
    "        for i in range(len(zeros)-2):\n",
    "            maxnum = max(maxnum, zeros[i+2] - zeros[i] - 1)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num = num&0Xffffffff\n",
    "        l = bin(num)[2:]\n",
    "        t = []\n",
    "        for c in l:\n",
    "            if len(t)==0:\n",
    "                t.append([c, 1])\n",
    "            else:\n",
    "                if t[-1][0] == c:\n",
    "                    t[-1][1] += 1\n",
    "                else:\n",
    "                    t.append([c, 1])\n",
    "        #print(t)\n",
    "\n",
    "        ret = 1\n",
    "        for i in range(len(t)):\n",
    "            if t[i][0] == '1':\n",
    "                ret = max(ret, t[i][1] + 1)\n",
    "            \n",
    "                if i<len(t)-2 and t[i+1][1] == 1:\n",
    "                    ret = max(ret, t[i][1] + t[i+2][1]+1)\n",
    "        return min(ret, 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0\n",
    "        insert=0\n",
    "        res=1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        dp = [0] * 2\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                dp[0] += 1\n",
    "                dp[1] += 1\n",
    "            else:\n",
    "                dp[1] = dp[0] + 1\n",
    "                dp[0] = 0\n",
    "            res = max(res, *dp)\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        count = count1 =maxcount1 =0\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                count+=1\n",
    "                count1+=1\n",
    "            else:\n",
    "                count1=count+1\n",
    "                count=0\n",
    "            maxcount1=max(maxcount1,count1)\n",
    "        return maxcount1\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0\n",
    "        insert=0\n",
    "        res=0\n",
    "        for i in range(32):\n",
    "            if num&(1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num = num&0xffffffff\n",
    "        l = num.bit_length()\n",
    "\n",
    "        r = [0]\n",
    "\n",
    "        # print(l)\n",
    "        for i in range(1,l):\n",
    "            if not num&1:\n",
    "                r.append(i)\n",
    "            num = num>>1\n",
    "        r.append(l+1)\n",
    "\n",
    "        # print(r)\n",
    "\n",
    "        for i in range(len(r)-1, 0, -1):\n",
    "            r[i] = r[i]-r[i-1]-1\n",
    "\n",
    "        for i in range(len(r)-1):\n",
    "            r[i] += (r[i+1]+1)\n",
    "\n",
    "\n",
    "        # print(r)\n",
    "        return min(max(r), 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                cur += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res, insert)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num==0 or num==1:return 1\n",
    "        val = []\n",
    "        tmp = 0\n",
    "        for i in range(32):\n",
    "            if (num>>i)&1==1:\n",
    "                if tmp>=0:\n",
    "                    tmp+=1\n",
    "                else:\n",
    "                    val.append(tmp)\n",
    "                    tmp=1\n",
    "            else:\n",
    "                if tmp>0:\n",
    "                    val.append(tmp)\n",
    "                    tmp = -1\n",
    "                else:\n",
    "                    tmp-=1\n",
    "        val.append(tmp)\n",
    "        sta = 1 if val[0]<0 else 0\n",
    "        res = val[sta]\n",
    "        n = len(val)\n",
    "        if n==1:return val[0]\n",
    "        for i in range(sta,n,2):\n",
    "            re=0\n",
    "            if i+2<n and val[i+1]==-1:\n",
    "                re += val[i+2]\n",
    "            re += val[i]+1\n",
    "            res = max(res,re)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        x = bin(num & 0xffffffff)[2:].split(\"0\")\n",
    "        n = len(x)\n",
    "        print(x)\n",
    "        if x:\n",
    "            res = len(x[0]) + 1\n",
    "        else:\n",
    "            res = 1\n",
    "        for i in range(n - 1):\n",
    "            res = max(res, len(x[i]) + len(x[i + 1]) + 1)\n",
    "        if res > 32:\n",
    "            return 32\n",
    "        return res\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num = num&0xffffffff\n",
    "        \n",
    "        l = num.bit_length()\n",
    "\n",
    "        r = [0]\n",
    "\n",
    "        # print(l)\n",
    "        p = 0\n",
    "        for i in range(1,l):\n",
    "            if not num&1:\n",
    "                r.append(i-p-1)\n",
    "                p = i\n",
    "            num = num>>1\n",
    "        r.append(l-p)\n",
    "\n",
    "        # print(r)\n",
    "\n",
    "        # for i in range(len(r)-1, 0, -1):\n",
    "        #     r[i] = r[i]-r[i-1]-1\n",
    "\n",
    "        for i in range(len(r)-1):\n",
    "            r[i] += (r[i+1]+1)\n",
    "\n",
    "\n",
    "        # print(r)\n",
    "        return min(max(r), 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0 # 当前位置为止连续1的个数\n",
    "        insert=0 # 变1之后，当前位置为止连续1的个数\n",
    "        res=1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i): # num的第i位为1\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else: # num的第i位为0\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0: # 处理负数\n",
    "            num = pow(2,32) - abs(num)\n",
    "        length = list(map(len,bin(num)[2:].ljust(32,'0').split('0'))) # 将num转为二进制，并以单个字符'0'分隔字符串,然后得出列表中每个字符串的长度,ljust用来前补'0'\n",
    "        return length[0] if len(length)==1 else max(length[i]+length[i+1] for i in range(len(length)-1))+1 # length长度为1说明32位二进制全为1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "\n",
    "        pre, cur = 0,0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur += 1\n",
    "            else:\n",
    "                res = max(res, pre+cur)\n",
    "                pre = cur+1\n",
    "                cur = 0\n",
    "        res = max(res, pre+cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur, ins, ans = 0, 0, 0\n",
    "        \n",
    "        for i in range(32):\n",
    "            if num & (1<<i) != 0:\n",
    "                cur += 1\n",
    "                ins += 1\n",
    "            else:\n",
    "                ins = cur + 1\n",
    "                cur = 0\n",
    "            ans = max(ans, ins)\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur=0  # 当前位置为止连续1的个数\n",
    "        insert=0  # 在当前位置变成1，往前数连续1的最大个数\n",
    "        res=1  # 保存insert最大值即可\n",
    "        for i in range(32):\n",
    "            if num&(1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        count = count1 =maxcount1 =0\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                count+=1\n",
    "                count1+=1\n",
    "            else:\n",
    "                count1=count+1\n",
    "                count=0\n",
    "            if maxcount1<count1:maxcount1=count1\n",
    "        return maxcount1\n",
    "            \n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        ans = 1\n",
    "        for i in range(32):\n",
    "            if num & 1 == 1:\n",
    "                cur += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            num = num >> 1\n",
    "            ans = max(ans, insert)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 0xffffffff + num + 1\n",
    "        binstr = bin(num)[2:]\n",
    "        binstr = '0' * (32 - len(binstr)) + binstr\n",
    "        idx = [-1, ]\n",
    "        for i, num in enumerate(binstr):\n",
    "            if num == '0':\n",
    "                idx.append(i)\n",
    "        idx.append(len(binstr))\n",
    "        if len(idx) == 2:\n",
    "            return 32\n",
    "        res = 0\n",
    "        for i in range(2, len(idx)):\n",
    "            res = max(res, idx[i] - idx[i-2])\n",
    "        return res - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 2**32 + num\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 2**32 - 1:\n",
    "            return 32\n",
    "        bits = []\n",
    "        zeros = [0]\n",
    "        while True:\n",
    "            bits.append(num % 2)\n",
    "            if bits[-1] == 0:\n",
    "                zeros.append(len(bits))\n",
    "            num = num // 2\n",
    "            if num == 0:\n",
    "                break\n",
    "        zeros.append(len(bits)+1)\n",
    "\n",
    "        # print(bits)\n",
    "        if len(zeros) == 2:\n",
    "            return zeros[1] - zeros[0]\n",
    "        # print(zeros)\n",
    "        maxnum = zeros[2] - zeros[0] - 1\n",
    "        for i in range(len(zeros)-2):\n",
    "            maxnum = max(maxnum, zeros[i+2] - zeros[i] - 1)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res='{:032b}'.format(num)\n",
    "        if(num < 0):\n",
    "            num = num&0xFFFFFFFF\n",
    "            res = (bin(num))[2:]\n",
    "        print(res)\n",
    "        print(len(res))\n",
    "        dp=[]\n",
    "        temp=0\n",
    "        for x in res:\n",
    "            if x=='0':\n",
    "                dp.append(temp)\n",
    "                temp=0\n",
    "            elif x=='1':\n",
    "                temp+=1\n",
    "        dp.append(temp)\n",
    "        temp=0\n",
    "        print(dp)\n",
    "        if len(dp)==1:\n",
    "            return min(dp[0]+1,32)\n",
    "        for x in range(1,len(dp)):\n",
    "            temp=max(temp,dp[x-1]+dp[x]+1)\n",
    "        return min(32,temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == -1:\n",
    "            return 32\n",
    "        \n",
    "        a = 0\n",
    "        if num < 0:\n",
    "            a = num\n",
    "            num = -num\n",
    "\n",
    "        bnum = bin(num)[2:]\n",
    "        if a < 0:\n",
    "            while len(bnum) % 4 != 0:\n",
    "                bnum = '0' + bnum\n",
    "                \n",
    "            lb = []\n",
    "            for i in bnum:\n",
    "                if i == '1':\n",
    "                    lb.append('0')\n",
    "                else:\n",
    "                    lb.append('1')\n",
    "   \n",
    "            \n",
    "            rlb = lb[::-1]\n",
    "            rn = len(rlb)\n",
    "    \n",
    "            t = \"\"\n",
    "            for i in range(rn):\n",
    "             \n",
    "                if rlb[i] == '0':\n",
    "                    t += '1'\n",
    "                    t = t + \"\".join(rlb[i + 1:])\n",
    "                    break\n",
    "                else:\n",
    "                    t += '0'\n",
    "            bnum = t\n",
    "            bnum = '1' * (32 - len(bnum)) + bnum[::-1]\n",
    "\n",
    "        res = []\n",
    "        c1, c2 = 0, 0\n",
    "        for i in range(len(bnum)):\n",
    "            if bnum[i] == '0':\n",
    "                c1 += 1\n",
    "                res.append(i)\n",
    "            else:\n",
    "                c2 += 1\n",
    "\n",
    "        if c1 == 0:\n",
    "            return c2 + 1\n",
    "        elif c1 == 1:\n",
    "            return c2 + 1\n",
    "        elif c1 == 2:\n",
    "            return res[1]\n",
    "        else:\n",
    "            ans = res[1]\n",
    "            for j in range(2, len(res)):\n",
    "                ans = max(ans, res[j] - res[j - 2] - 1)\n",
    "            ans = max(ans, len(bnum) - res[-2] -1)\n",
    "            return min(32,ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        def count_bit(n:str):\n",
    "            max_n = 0\n",
    "            count = 0\n",
    "            for c in n:\n",
    "                if c == '1':\n",
    "                    count += 1\n",
    "                else:\n",
    "                    max_n = max(max_n, count)\n",
    "                    count = 0\n",
    "            max_n = max(max_n, count)\n",
    "            return max_n\n",
    "        \n",
    "        if num < 0:\n",
    "            for i in range(32):\n",
    "                num ^= 1 << i\n",
    "            num += 1\n",
    "\n",
    "        s = '0' + bin(num)[2:]\n",
    "        zero_pos = []\n",
    "        for i,c in enumerate(s):\n",
    "            if c == '0':\n",
    "                zero_pos.append(i)\n",
    "        \n",
    "        max_n = 0\n",
    "        for i in zero_pos:\n",
    "            max_n = max(max_n, count_bit(s[:i] + '1' + s[i+1:]))\n",
    "            \n",
    "        return max_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = 2**32 + num\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        if num == 2**32 - 1:\n",
    "            return 32\n",
    "        bits = []\n",
    "        zeros = [0]\n",
    "        while True:\n",
    "            bits.append(num % 2)\n",
    "            if bits[-1] == 0:\n",
    "                zeros.append(len(bits))\n",
    "            num = num // 2\n",
    "            if num == 0:\n",
    "                break\n",
    "        zeros.append(len(bits)+1)\n",
    "\n",
    "        # print(bits)\n",
    "        if len(zeros) == 2:\n",
    "            return zeros[1] - zeros[0]\n",
    "        # print(zeros)\n",
    "        maxnum = 0\n",
    "        for i in range(len(zeros)-2):\n",
    "            maxnum = max(maxnum, zeros[i+2] - zeros[i] - 1)\n",
    "        return maxnum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur, pre = 0, 0\n",
    "        ans = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur += 1\n",
    "            else:\n",
    "                ans = max(ans, cur + pre)\n",
    "                cur, pre = 0, cur + 1\n",
    "        ans = max(ans, cur + pre)\n",
    "        return ans\n",
    "\n",
    "        # pre, cur =0, 0\n",
    "        # res = 1\n",
    "        # for i in range(32):\n",
    "        #     if num & (1<<i):\n",
    "        #         cur+=1\n",
    "        #     else:\n",
    "        #         res=max(res, pre+cur)\n",
    "        #         pre = cur +1\n",
    "        #         cur = 0\n",
    "        # res=max(res, pre+cur)\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        c = 0\n",
    "        insert = 0\n",
    "        r = 1\n",
    "        for i in range(32):\n",
    "            if num &(1<<i):\n",
    "                c += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = c + 1\n",
    "                c = 0\n",
    "            r = max(r,insert)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "\n",
    "        cur=0\n",
    "        insert=0\n",
    "        res=1\n",
    "\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur+=1\n",
    "                insert+=1\n",
    "            else:\n",
    "                insert=cur+1\n",
    "                cur=0\n",
    "            res=max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        pre = 0\n",
    "        res = 0\n",
    "\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                cur += 1\n",
    "                pre += 1\n",
    "            else:\n",
    "                pre = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res, pre)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        ans = pre = cur = 0\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                cur += 1\n",
    "            else:\n",
    "                ans = max(ans, pre + cur)\n",
    "                pre = cur + 1\n",
    "                cur = 0\n",
    "        ans = max(ans, pre + cur)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        curr = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1 << i):\n",
    "                curr += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = curr + 1\n",
    "                curr = 0\n",
    "            res = max(res, insert)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        left = 0\n",
    "        counter = 0 \n",
    "        res = 0\n",
    "        for right in range(0 ,32): \n",
    "            counter += num >> right & 1 ^ 1\n",
    "            while counter > 1:\n",
    "                counter -= num >> left & 1 ^ 1\n",
    "                left += 1\n",
    "            res = max(right-left+1, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num==0 or num==1:return 1\n",
    "        val = []\n",
    "        tmp = 0\n",
    "        for i in range(32):\n",
    "            if (num>>i)&1==1:\n",
    "                if tmp>=0:\n",
    "                    tmp+=1\n",
    "                else:\n",
    "                    val.append(tmp)\n",
    "                    tmp=1\n",
    "            else:\n",
    "                if tmp>0:\n",
    "                    val.append(tmp)\n",
    "                    tmp = -1\n",
    "                else:\n",
    "                    tmp-=1\n",
    "        val.append(tmp)\n",
    "        sta = 1 if val[0]<0 else 0\n",
    "        res = val[sta]\n",
    "        n = len(val)\n",
    "        if n==1:return val[0]\n",
    "        for i in range(sta,n,2):\n",
    "            re=0\n",
    "            if i+2<n and val[i+1]==-1:\n",
    "                re += val[i+2]\n",
    "            re += val[i]+1\n",
    "            res = max(res,re)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        left = 0\n",
    "        counter = 0 \n",
    "        res = 0\n",
    "        for right in range(0 ,32): \n",
    "            counter += num >> right & 1 ^ 1\n",
    "            while counter > 1:\n",
    "                counter -= num >> left & 1 ^ 1\n",
    "                left += 1\n",
    "            res = max(right-left+1, res)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseBits(self, num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num < 0:\n",
    "            num = abs(num)\n",
    "            for i in range(32, -1, -1):\n",
    "                if num >> i & 1 == 0:\n",
    "                    num |= 1 << i\n",
    "                else: num ^= 1 << i\n",
    "            num += 1\n",
    "        left = [0] * 32\n",
    "        right = [0] * 32\n",
    "        for i in range(32):\n",
    "            if num >> i & 1: left[i] += left[i - 1] + 1\n",
    "            else: left[i] = 0\n",
    "        for i in range(31, -1, -1):\n",
    "            if num >> i & 1: right[i] += right[(i + 1) % 32] + 1\n",
    "            else: right[i] = 0\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            if num >> i & 1 == 0:\n",
    "                a = 0 if i - 1 < 0 else left[i - 1]\n",
    "                b = 0 if i + 1 == 32 else right[i + 1]\n",
    "                res = max(res, a + b + 1)\n",
    "        return max(res, max(left), max(right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # 需要注意这里是补码\n",
    "        if num<0:\n",
    "            num = bin(num & 0xffffffff)[2:]\n",
    "        else:\n",
    "            num = bin(num)[2:]\n",
    "            num = '0'*(32-len(num))+num\n",
    "        num = [int(i) for i in num]\n",
    "        @cache\n",
    "        def dp(i, k):\n",
    "            if k<0:\n",
    "                return 0\n",
    "            if i==0:\n",
    "                return int(k==1 or num[0]==1)\n",
    "            if num[i]==1:\n",
    "                return dp(i-1, k)+1\n",
    "            else:\n",
    "                return dp(i-1, k-1)+k\n",
    "        res = 0\n",
    "        for i in range(len(num)):\n",
    "            res = max(res, dp(i, 1))\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == -1:\n",
    "            return 32\n",
    "        num_bin = self.getBin(num)\n",
    "        # 思路 对二进制列表进行分割，分隔符为0\n",
    "        # 对剩余多个1的数组，只需考虑连续的两个和最大，并加一即是最后结果\n",
    "        num_spl = num_bin.split(\"0\")\n",
    "        max_len = 0\n",
    "        for i in range(len(num_spl) - 1):\n",
    "                max_len = max(max_len,len(num_spl[i])+len(num_spl[i+1]))\n",
    "        return max_len + 1\n",
    "\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "\n",
    "            注意为什么这里需要用32位呢，因为需要考虑负数\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return binary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        # cur, pre = 0, 0\n",
    "        # ans = 0\n",
    "        # while num:\n",
    "        #     if num % 2 == 0:\n",
    "        #         ans = max(ans, cur + pre + 1)\n",
    "        #         cur, pre = 0, cur\n",
    "        #     else:\n",
    "        #         cur += 1\n",
    "        #     num = num >> 1\n",
    "        # ans = max(ans, cur + pre + 1)\n",
    "        # return ans\n",
    "        pre, cur =0, 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "                cur+=1\n",
    "            else:\n",
    "                res=max(res, pre+cur)\n",
    "                pre = cur +1\n",
    "                cur = 0\n",
    "        res=max(res, pre+cur)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res = []\n",
    "        i = 32\n",
    "        while i:\n",
    "            temp = num & 1\n",
    "            res.append(temp)\n",
    "            num = num >> 1\n",
    "            i -= 1\n",
    "        cnt = 0\n",
    "        q = []\n",
    "        max_length = 0\n",
    "        for i in res:\n",
    "            if i == 1:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                if cnt == 0:\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    max_length = max(max_length, len(q))\n",
    "                    cnt -= 1\n",
    "                    while True:\n",
    "                        temp = q.pop(0)\n",
    "                        if temp == 0:\n",
    "                            break\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        if max_length == 0:\n",
    "            max_length = len(q)\n",
    "        else:\n",
    "            if cnt == 1 and res[-1] == 1:\n",
    "                max_length = max(max_length, len(q))\n",
    "            else:\n",
    "                max_length = max(max_length, len(q))\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res = []\n",
    "        i = 32\n",
    "        while i:\n",
    "            temp = num & 1\n",
    "            res.append(temp)\n",
    "            num = num >> 1\n",
    "            i -= 1\n",
    "        cnt = 0\n",
    "        q = []\n",
    "        max_length = 0\n",
    "        for i in res:\n",
    "            if i == 1:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                if cnt == 0:\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    max_length = max(max_length, len(q))\n",
    "                    cnt -= 1\n",
    "                    while True:\n",
    "                        temp = q.pop(0)\n",
    "                        if temp == 0:\n",
    "                            break\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        max_length = max(max_length, len(q))\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == -1:\n",
    "            return 32\n",
    "        \n",
    "        a = 0\n",
    "        if num < 0:\n",
    "            a = num\n",
    "            num = -num\n",
    "\n",
    "        bnum = bin(num)[2:]\n",
    "        if a < 0:\n",
    "            while len(bnum) % 4 != 0:\n",
    "                bnum = '0' + bnum\n",
    "                \n",
    "            lb = []\n",
    "            for i in bnum:\n",
    "                if i == '1':\n",
    "                    lb.append('0')\n",
    "                else:\n",
    "                    lb.append('1')\n",
    "   \n",
    "            \n",
    "            rlb = lb[::-1]\n",
    "            rn = len(rlb)\n",
    "    \n",
    "            t = \"\"\n",
    "            for i in range(rn):\n",
    "             \n",
    "                if rlb[i] == '0':\n",
    "                    t += '1'\n",
    "                    t = t + \"\".join(rlb[i + 1:])\n",
    "                    break\n",
    "                else:\n",
    "                    t += '0'\n",
    "            bnum = t\n",
    "            bnum = '1' * (32 - len(bnum)) + bnum[::-1]\n",
    "\n",
    "        res = []\n",
    "        c1, c2 = 0, 0\n",
    "        for i in range(len(bnum)):\n",
    "            if bnum[i] == '0':\n",
    "                c1 += 1\n",
    "                res.append(i)\n",
    "            else:\n",
    "                c2 += 1\n",
    "\n",
    "        if c1 == 0:\n",
    "            return c2 + 1\n",
    "        elif c1 == 1:\n",
    "            return c2 + 1\n",
    "        elif c1 == 2:\n",
    "            return res[1]\n",
    "        else:\n",
    "            ans = res[1]\n",
    "            for j in range(2, len(res)):\n",
    "                ans = max(ans, res[j] - res[j - 2] - 1)\n",
    "            ans = max(ans, len(bnum) - res[-2] -1)\n",
    "            return min(32,ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        res = []\n",
    "        i = 32\n",
    "        while i:\n",
    "            temp = num & 1\n",
    "            res.append(temp)\n",
    "            num = num >> 1\n",
    "            i -= 1\n",
    "        cnt = 0\n",
    "        q = []\n",
    "        max_length = 0\n",
    "        for i in res:\n",
    "            if i == 1:\n",
    "                q.append(i)\n",
    "            else:\n",
    "                if cnt == 0:\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    max_length = max(max_length, len(q))\n",
    "                    cnt -= 1\n",
    "                    while True:\n",
    "                        temp = q.pop(0)\n",
    "                        if temp == 0:\n",
    "                            break\n",
    "                    q.append(i)\n",
    "                    cnt += 1\n",
    "        if max_length == 0:\n",
    "            max_length = len(q)\n",
    "        else:\n",
    "            max_length = max(max_length, len(q))\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for _ in range(32):\n",
    "            if num & 1 == 1:\n",
    "                cur += 1\n",
    "                insert += 1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res, insert)\n",
    "            num >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "      \n",
    "        cur = 0\n",
    "        insert = 0\n",
    "        res = 1\n",
    "        for i in range(32):\n",
    "            if num & (1<<i):\n",
    "               cur += 1\n",
    "               insert +=1\n",
    "            else:\n",
    "                insert = cur + 1\n",
    "                cur = 0\n",
    "            res = max(res,insert)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        num_bin = self.getBin(num)\n",
    "        if 1 not in num_bin:\n",
    "            return 1\n",
    "        if 0 not in num_bin:\n",
    "            return len(num_bin)\n",
    "        # 思路：找出每个0的index记录下来，每次循环让一个0变成1，记录下当次变成0的最大长度，每次迭代更新\n",
    "        zero_index = []\n",
    "        for i in range(len(num_bin)):\n",
    "            if num_bin[i] == 0:\n",
    "                zero_index.append(i)\n",
    "        max_len = 0\n",
    "        for each in zero_index:\n",
    "            num_bin[each] = 1\n",
    "            temp_len = 0\n",
    "            if 0 not in num_bin:\n",
    "                return len(num_bin)\n",
    "            for i in range(len(num_bin)):\n",
    "                if num_bin[i] == 1:\n",
    "                    temp_len += 1\n",
    "                if num_bin[i] == 0 or (i == len(num_bin) - 1):\n",
    "                    max_len = max(max_len,temp_len)\n",
    "                    temp_len = 0\n",
    "            num_bin[each] = 0  # 这一步特别关键，一定要重新置为0\n",
    "        return max_len\n",
    "\n",
    "    def getBin(self,num):\n",
    "        \"\"\" 需要获得num的32为二进制码，注意负数应该是用补码来存放，正数的补码等于原码\n",
    "            相当于需要求num的32位补码\n",
    "            这里采用内置函数bin\n",
    "        \"\"\"\n",
    "        if num >= 0:\n",
    "            binary = bin(num)[2:]  # 对于正数，直接使用内置函数 bin 来获取二进制表示\n",
    "            binary = binary.zfill(32)  # 补足到32位\n",
    "        else:\n",
    "            binary = bin(2 ** 32 + num)[2:]  # 对于负数，先转换为补码形式，然后获取二进制表示\n",
    "        return [int(i) for i in binary]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, num: int) -> int:\n",
    "        if num == 0:\n",
    "            return 1\n",
    "        m = 0\n",
    "        s = '0' + bin(num)[2:] if num > 0 else bin(num & 0xffffffff)[2:]\n",
    "        dp = [0] * len(s)\n",
    "\n",
    "        def dfs(dp: List, index: int, s: str, c: bool):\n",
    "            nonlocal m\n",
    "            if index == len(s):\n",
    "                return\n",
    "            if s[index] == '1':\n",
    "                dp[index] = dp[index - 1] + 1 if index > 0 else 1\n",
    "                m = max(m, dp[index])\n",
    "                dfs(dp, index + 1, s, c)\n",
    "            else:\n",
    "                if not c:\n",
    "                    dp[index] = 0\n",
    "                    dfs(dp, index + 1, s, c)\n",
    "                else:\n",
    "                    dp[index] = 0\n",
    "                    dfs(dp, index + 1, s, True)\n",
    "                    # 这个策略影响的是之后的dp值，所以删去\n",
    "                    for i in range(index + 1, len(dp)):\n",
    "                        dp[i] = 0\n",
    "                    temp = s[:index] + '1' + s[index + 1:]\n",
    "                    dp[index] = dp[index - 1] + 1 if index > 0 else 1\n",
    "                    m = max(m, dp[index])\n",
    "                    dfs(dp, index + 1, temp, False)\n",
    "                    for i in range(index + 1, len(dp)):\n",
    "                        dp[i] = 0\n",
    "\n",
    "        dfs(dp, 0, s, True)\n",
    "        return m\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        j = 0\n",
    "        for i in range(32):\n",
    "            j = j<<1\n",
    "            j += int(str(n%2))\n",
    "            n = n>>1\n",
    "        return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        t = 1<<31\n",
    "        while n:\n",
    "            ans += (n%2) * t\n",
    "            n >>= 1\n",
    "            t >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        t = 1<<31\n",
    "        while n:\n",
    "            ans += (n%2) * t\n",
    "            n >>= 1\n",
    "            t >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        bin_str = bin(n)[2:]\n",
    "        bin_str = bin_str.zfill(32)[::-1]\n",
    "        return int(bin_str, base=2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reverseBits(self, n: int) -> int:\r\n",
    "        result = 0\r\n",
    "        for i in range(32):\r\n",
    "            bit = n & 1\r\n",
    "            n = n >> 1\r\n",
    "            result = result << 1 | bit\r\n",
    "        return result\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "\n",
    "        res = n & 1\n",
    "\n",
    "        for i in range(31):\n",
    "            res = res << 1\n",
    "            n = n >> 1\n",
    "            res += n & 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        recorder = 0\n",
    "        count = 31\n",
    "        while n:\n",
    "            recorder |= (n&1) << count\n",
    "            count -= 1\n",
    "            n >>= 1\n",
    "        return recorder\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        res=0\n",
    "        power=31\n",
    "        while n:\n",
    "            res+=(n&1)<<power   #安排翻转之后第power位的数字 为啥不是32呢起始\n",
    "            n=n>>1\n",
    "            power-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        ret = 0\n",
    "        for i in range(32):\n",
    "            ret <<= 1\n",
    "            ret |= (n&1)\n",
    "            n >>= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        return int(\"0b\"+bin(n)[2:].zfill(32)[::-1],2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reverseBits(self, n: int) -> int:\r\n",
    "        res = 0\r\n",
    "        for i in range(32):\r\n",
    "            res <<= 1\r\n",
    "            res += n & 1\r\n",
    "            n >>= 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        return int(bin(n)[2:].rjust(32, '0')[::-1], 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        n = (n >> 16) | (n << 16);\n",
    "        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);\n",
    "        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);\n",
    "        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);\n",
    "        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);\n",
    "        return n;\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res <<= 1\n",
    "            res |= n & 1\n",
    "            n >>= 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        # ans=0\n",
    "        # dct={}\n",
    "        # n=str(n)\n",
    "        # for i,j in enumerate(n):\n",
    "        #     j=int(j)\n",
    "        #     for k in range(i):\n",
    "        #         j*=2\n",
    "        #     ans+=j\n",
    "        # # print(dct)\n",
    "        # return ans\n",
    "        print(bin(n))\n",
    "        n=bin(n)[2:]\n",
    "        if len(n)<32:\n",
    "            for i in range(32-len(n)):\n",
    "                n='0'+n\n",
    "        print(n)\n",
    "        # n=str(n)\n",
    "        def sum(lens,n):\n",
    "            if lens==1:\n",
    "                return int(n[lens-1])*(2**(lens-1))\n",
    "                # print(int(n[lens-1])*(2**(lens-1)))\n",
    "            return int(n[lens-1])*(2**(lens-1))+sum(lens-1,n)\n",
    "        return sum(len(n),n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        bitmap = {0: 0, 1: 128, 2: 64, 3: 192, 4: 32, 5: 160, 6: 96, 7: 224, 8: 16, 9: 144, 10: 80, 11: 208, 12: 48, 13: 176, 14: 112, 15: 240, 16: 8, 17: 136, 18: 72, 19: 200, 20: 40, 21: 168, 22: 104, 23: 232, 24: 24, 25: 152, 26: 88, 27: 216, 28: 56, 29: 184, 30: 120, 31: 248, 32: 4, 33: 132, 34: 68, 35: 196, 36: 36, 37: 164, 38: 100, 39: 228, 40: 20, 41: 148, 42: 84, 43: 212, 44: 52, 45: 180, 46: 116, 47: 244, 48: 12, 49: 140, 50: 76, 51: 204, 52: 44, 53: 172, 54: 108, 55: 236, 56: 28, 57: 156, 58: 92, 59: 220, 60: 60, 61: 188, 62: 124, 63: 252, 64: 2, 65: 130, 66: 66, 67: 194, 68: 34, 69: 162, 70: 98, 71: 226, 72: 18, 73: 146, 74: 82, 75: 210, 76: 50, 77: 178, 78: 114, 79: 242, 80: 10, 81: 138, 82: 74, 83: 202, 84: 42, 85: 170, 86: 106, 87: 234, 88: 26, 89: 154, 90: 90, 91: 218, 92: 58, 93: 186, 94: 122, 95: 250, 96: 6, 97: 134, 98: 70, 99: 198, 100: 38, 101: 166, 102: 102, 103: 230, 104: 22, 105: 150, 106: 86, 107: 214, 108: 54, 109: 182, 110: 118, 111: 246, 112: 14, 113: 142, 114: 78, 115: 206, 116: 46, 117: 174, 118: 110, 119: 238, 120: 30, 121: 158, 122: 94, 123: 222, 124: 62, 125: 190, 126: 126, 127: 254, 128: 1, 129: 129, 130: 65, 131: 193, 132: 33, 133: 161, 134: 97, 135: 225, 136: 17, 137: 145, 138: 81, 139: 209, 140: 49, 141: 177, 142: 113, 143: 241, 144: 9, 145: 137, 146: 73, 147: 201, 148: 41, 149: 169, 150: 105, 151: 233, 152: 25, 153: 153, 154: 89, 155: 217, 156: 57, 157: 185, 158: 121, 159: 249, 160: 5, 161: 133, 162: 69, 163: 197, 164: 37, 165: 165, 166: 101, 167: 229, 168: 21, 169: 149, 170: 85, 171: 213, 172: 53, 173: 181, 174: 117, 175: 245, 176: 13, 177: 141, 178: 77, 179: 205, 180: 45, 181: 173, 182: 109, 183: 237, 184: 29, 185: 157, 186: 93, 187: 221, 188: 61, 189: 189, 190: 125, 191: 253, 192: 3, 193: 131, 194: 67, 195: 195, 196: 35, 197: 163, 198: 99, 199: 227, 200: 19, 201: 147, 202: 83, 203: 211, 204: 51, 205: 179, 206: 115, 207: 243, 208: 11, 209: 139, 210: 75, 211: 203, 212: 43, 213: 171, 214: 107, 215: 235, 216: 27, 217: 155, 218: 91, 219: 219, 220: 59, 221: 187, 222: 123, 223: 251, 224: 7, 225: 135, 226: 71, 227: 199, 228: 39, 229: 167, 230: 103, 231: 231, 232: 23, 233: 151, 234: 87, 235: 215, 236: 55, 237: 183, 238: 119, 239: 247, 240: 15, 241: 143, 242: 79, 243: 207, 244: 47, 245: 175, 246: 111, 247: 239, 248: 31, 249: 159, 250: 95, 251: 223, 252: 63, 253: 191, 254: 127, 255: 255}\n",
    "        result = 0\n",
    "        for i in range(4):\n",
    "            result <<= 8\n",
    "            result |= bitmap[n & 255]\n",
    "            n >>= 8\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        s=format(n, \"032b\")\n",
    "        s1=list(s)\n",
    "        s2=''.join(s1[::-1])\n",
    "        return int(s2,2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # @param n, an integer\n",
    "    # @return an integer\n",
    "    def reverseBits(self, n):\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res = (res << 1) | (n & 1)\n",
    "            n >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            res = (res << 1) | (n & 1)\n",
    "            n = n >> 1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        INT_MAX = 2**31 - 1  # 32-bit integer max\n",
    "\n",
    "        ret = 0\n",
    "        neg = x < 0\n",
    "        x = abs(x)\n",
    "        while x != 0:\n",
    "            digit = x % 10  # Get the last digit\n",
    "\n",
    "            # Check for overflow\n",
    "            if ret > (INT_MAX - digit) // 10:\n",
    "                return 0\n",
    "\n",
    "            ret = ret * 10 + digit\n",
    "            x = int(x // 10)  # Use integer division to reduce x\n",
    "\n",
    "        return -ret if neg else ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if x == 0:\n",
    "        #     return x\n",
    "        # flag = False\n",
    "        # if x<0:\n",
    "        #     flag=True\n",
    "        #     x = -x\n",
    "        # x = list(str(x))\n",
    "        # x.reverse()\n",
    "        # x = x[1:] if x[-1]=='0' else x\n",
    "        # x = int(''.join(x))\n",
    "        # if flag == True:\n",
    "        #     x = -x\n",
    "        # return x if x>=-2147483648 and x<2147483648 else 0\n",
    "    \n",
    "        # res = 0\n",
    "        # flag = False\n",
    "        # if x < 0:\n",
    "        #     flag = True\n",
    "        #     x = -x\n",
    "        # while x != 0:\n",
    "        #     a = x % 10\n",
    "        #     x = x // 10\n",
    "        #     res = res * 10 + a\n",
    "        # if flag:\n",
    "        #     res = -res\n",
    "        # return res if res >= -2147483648 and res <= 2147483647 else 0\n",
    "        \n",
    "        # y = int(str(x)[::-1]) if x > 0 else -int(str(-x)[::-1])\n",
    "        # return y if y>=-2147483648 and y<2147483648 else 0\n",
    "        \n",
    "        # sign = [1,-1][x < 0]\n",
    "        # y = sign*(int(str(abs(x))[::-1]))\n",
    "        # return y if y>=-2147483648 and y<2147483648 else 0\n",
    "        if x<0:\n",
    "            Y=int('-'+str(x)[::-1].strip('0').replace(\"-\",''))\n",
    "        elif x>0:\n",
    "            Y=int(str(x)[::-1].strip('0'))\n",
    "        else:\n",
    "            Y=0\n",
    "        return Y if (-(2**31))<Y<((2**31)-1) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if x == 0:\n",
    "        #     return x\n",
    "        # flag = False\n",
    "        # if x<0:\n",
    "        #     flag=True\n",
    "        #     x = -x\n",
    "        # x = list(str(x))\n",
    "        # x.reverse()\n",
    "        # x = x[1:] if x[-1]=='0' else x\n",
    "        # x = int(''.join(x))\n",
    "        # if flag == True:\n",
    "        #     x = -x\n",
    "        # return x if x>=-2147483648 and x<2147483648 else 0\n",
    "    \n",
    "        # res = 0\n",
    "        # flag = False\n",
    "        # if x < 0:\n",
    "        #     flag = True\n",
    "        #     x = -x\n",
    "        # while x != 0:\n",
    "        #     a = x % 10\n",
    "        #     x = x // 10\n",
    "        #     res = res * 10 + a\n",
    "        # if flag:\n",
    "        #     res = -res\n",
    "        # return res if res >= -2147483648 and res <= 2147483647 else 0\n",
    "        \n",
    "        # y = int(str(x)[::-1]) if x > 0 else -int(str(-x)[::-1])\n",
    "        # return y if y>=-2147483648 and y<2147483648 else 0\n",
    "        \n",
    "        sign = [1,-1][x < 0]\n",
    "        y = sign*(int(str(abs(x))[::-1]))\n",
    "        return y if y>=-2147483648 and y<2147483648 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        x =str(x)\n",
    "        if x[0] == '-':\n",
    "            y= [x[0], x[:0:-1]]\n",
    "            y = int(''.join(a for a in y))\n",
    "        else:\n",
    "            y = int(x[::-1])        \n",
    "        if y >2**31 -1 or y<-2**31:\n",
    "            return 0\n",
    "        else:\n",
    "            return y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        rev = 0\n",
    "        flag = False\n",
    "        if x<0:\n",
    "            flag = True\n",
    "            x = -x\n",
    "        while(x!=0):\n",
    "            print (x)\n",
    "            pop = x % 10\n",
    "            x = (x//10)\n",
    "            rev = rev * 10 + pop\n",
    "        if flag:\n",
    "            rev = -rev\n",
    "        return rev if rev<pow(2,31)-1 and rev>-pow(2,31) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        if x==0:\n",
    "            return 0\n",
    "        str_x = str(x)\n",
    "        x = ''\n",
    "        if str_x[0] == '-':\n",
    "            x += '-'\n",
    "        x += str_x[len(str_x)-1::-1].lstrip(\"0\").rstrip(\"-\")\n",
    "        x = int(x)\n",
    "        if -2**31<x<2**31-1:\n",
    "            return x\n",
    "        return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: 'int') -> 'int':\n",
    "        \n",
    "        if x > 0 :\n",
    "            num_str = str(x)\n",
    "            length = len(num_str)\n",
    "            new_str = []\n",
    "            for i in range(length):\n",
    "                print(i)\n",
    "                new_str.append(num_str[length - i - 1])\n",
    "                a = \"\".join(new_str)\n",
    "                print(a)\n",
    "            for i in range(len(a)):\n",
    "                if a[0] == '0':\n",
    "                     a = a[1:]\n",
    "            a = eval(a)\n",
    "            \n",
    "        elif x < 0 :\n",
    "            x = -x\n",
    "            num_str = str(x)\n",
    "            length = len(num_str)\n",
    "            new_str = []\n",
    "            for i in range(length):\n",
    "                print(i)\n",
    "                new_str.append(num_str[length - i - 1])\n",
    "                a = \"\".join(new_str)\n",
    "                print(a)\n",
    "            for i in range(len(a)):\n",
    "                if a[0] == '0':\n",
    "                     a = a[1:]\n",
    "            a = -eval(a)\n",
    "        \n",
    "        else :\n",
    "            a = 0\n",
    "        \n",
    "        if a > -2**31 and a < 2**31 - 1 :\n",
    "            return a\n",
    "        else :\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res=0\n",
    "        \n",
    "        if x>=0:\n",
    "            flag=1\n",
    "        else:\n",
    "            flag=-1\n",
    "            \n",
    "        x=abs(x)\n",
    "        \n",
    "        while x!=0:\n",
    "            res=res*10+x%10\n",
    "            x=int(x/10)\n",
    "            \n",
    "        if res>2**31-1 or res<-2**31:\n",
    "            return 0\n",
    "        \n",
    "        return res*flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if x > -2**31 and x < 0:\n",
    "            t = -x\n",
    "            a = str(t)\n",
    "            b = a[::-1]\n",
    "            c = int(b)\n",
    "            d = -c\n",
    "            if d > -2**31 and d <0:\n",
    "                return d\n",
    "            else:\n",
    "                return 0\n",
    "        elif x>=0 and x <2**31-1:\n",
    "            a = str(x)\n",
    "            b = a[::-1]\n",
    "            c = int(b)\n",
    "            if c>=0 and c<2**31-1:\n",
    "                return c\n",
    "            else:\n",
    "                return 0\n",
    "        else:\n",
    "            return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if x >= 0:\n",
    "            flag = 1\n",
    "        else:\n",
    "            flag = -1\n",
    "        abs_x = abs(x)\n",
    "        answer = 0\n",
    "        while abs_x > 0:\n",
    "            answer = answer * 10 + abs_x % 10\n",
    "            abs_x = abs_x // 10\n",
    "\n",
    "        answer = flag * answer\n",
    "        return answer if answer < 2147483648 and answer >= -2147483648 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        maxNum = 2**31 - 1\n",
    "        minNum = -2**31\n",
    "        strx = str(x)\n",
    "        fuhao = strx[0]\n",
    "        if fuhao=='-':\n",
    "            strx = strx[1:]            \n",
    "        else:\n",
    "            fuhao='0'        \n",
    "        revx = strx[::-1]\n",
    "        \n",
    "        result = int(fuhao+revx)\n",
    "        if result>maxNum or result <minNum:\n",
    "            return 0\n",
    "        else:\n",
    "            return result\n",
    "        \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    m_Min = -2**31\n",
    "    m_Max = 2**31 - 1\n",
    "\n",
    "    def reverse(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if x < 0:\n",
    "            str_x = str(abs(x))\n",
    "            x = \"-\"\n",
    "        else:\n",
    "            str_x = str(x)\n",
    "            x = \"\"\n",
    "        x += str_x[::-1]\n",
    "        result = int(x)\n",
    "        print(result)\n",
    "        if result < self.m_Min or result > self.m_Max:\n",
    "            return 0\n",
    "        return result\n",
    "\n",
    "\n",
    "Solution().reverse(123)\n",
    "Solution().reverse(-123)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        s = str(x)\n",
    "        sign = ''\n",
    "        if s.startswith('-'):\n",
    "            sign = '-'\n",
    "            s = s[1:]\n",
    "        s = s[::-1]\n",
    "        while s.startswith('0'):\n",
    "            s = s[1:]\n",
    "        if s == '':\n",
    "            return 0\n",
    "        if sign is '' and int(s) > 2**31 -1:\n",
    "            return 0\n",
    "        if sign == '-' and int(s) > 2**31:\n",
    "            return 0\n",
    "        s = sign + s\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        '''\n",
    "        f = False\n",
    "        if x < 0:\n",
    "            f = True\n",
    "        x = str(x)[::-1].strip('-')\n",
    "        if f:\n",
    "            x = -int(x)\n",
    "        else:\n",
    "            x = int(x)\n",
    "        if -2**31 <= x <= 2**31-1:\n",
    "            return x\n",
    "        return 0\n",
    "        '''\n",
    "        y, res = abs(x), 0\n",
    "        boundary = 1<<31 if x < 0 else (1<<31)-1\n",
    "        while y != 0:\n",
    "            res = res*10 + y%10\n",
    "            if res > boundary:\n",
    "                return 0\n",
    "            y //=10\n",
    "        return res if x>0 else -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        a = str(x)\n",
    "        if x > 0 :\n",
    "            a = a[::-1]\n",
    "            e = int(a)\n",
    "            if e > (2**31)-1:\n",
    "                return 0\n",
    "            return e\n",
    "        elif x < 0 :\n",
    "            b = -x\n",
    "            c = str(b)\n",
    "            c = c[::-1]\n",
    "            d =-int(c)\n",
    "            if d <-2**31:\n",
    "                return 0\n",
    "            return d\n",
    "        elif x== 0:\n",
    "            return x\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        l = [i for i in str(x)]\n",
    "        if x.bit_length() <= 31:\n",
    "            if x > 0:\n",
    "                l.reverse()\n",
    "                result = int(''.join(l))\n",
    "                if result.bit_length() <= 31:\n",
    "                    return result\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                temp = l[1:]\n",
    "                temp.reverse()\n",
    "                l = [l[0]] + temp\n",
    "                result = int(''.join(l))\n",
    "                if result.bit_length() <= 31:\n",
    "                    return result\n",
    "                else:\n",
    "                    return 0\n",
    "        else:\n",
    "            return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        flag=1\n",
    "        if x<0:\n",
    "            flag=-1\n",
    "            x=-x\n",
    "        ans=0\n",
    "        while x:\n",
    "            if ans>214748364:\n",
    "                return 0\n",
    "            elif ans==214748364: \n",
    "                ans*=10\n",
    "                if flag<0 and x%10>2 or flag>0 and x%10>1:\n",
    "                    return 0\n",
    "            else:\n",
    "                ans*=10\n",
    "            ans+=x%10\n",
    "            x//=10\n",
    "        return ans*flag\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reverse(self, x: int) -> int:\r\n",
    "        s = str(x)\r\n",
    "        if s[0] == '-':\r\n",
    "            x = int('-' + s[-1:-len(s):-1])\r\n",
    "        else:\r\n",
    "            x = int(s[::-1])\r\n",
    "        return x if -2147483648< x <2147483647 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        if x<0:\n",
    "            a = -int(str(abs(x))[::-1])\n",
    "        else:\n",
    "            a = int(str(abs(x))[::-1])\n",
    "        return a if -2147483648< a <2147483647 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        # 正数情况\n",
    "        a=[]\n",
    "        res=0\n",
    "        limit = 2**31\n",
    "        if x==0:\n",
    "            return 0\n",
    "        if res>=(limit):\n",
    "                return 0\n",
    "        if x>0:\n",
    "            if x<10:\n",
    "                return x\n",
    "           \n",
    "            while(x>=10):\n",
    "                b=x%10\n",
    "                x=int(x/10)\n",
    "                a.append(b)\n",
    "            a.append(x)\n",
    "            lenth=len(a)\n",
    "            \n",
    "            for num in a:\n",
    "                res=res+num*(10**(lenth-1))\n",
    "                lenth=lenth-1\n",
    "            if res>=(limit):\n",
    "                return 0\n",
    "            return res\n",
    "        if x<0:\n",
    "            x=x*-1\n",
    "            if x<10:\n",
    "                return x*-1\n",
    "      \n",
    "            while(x>=10):\n",
    "                b=x%10\n",
    "                x=int(x/10)\n",
    "                a.append(b)\n",
    "            a.append(x)\n",
    "            lenth=len(a)\n",
    "            for num in a:\n",
    "                res=res+num*(10**(lenth-1))\n",
    "                lenth=lenth-1\n",
    "            if res>=(limit):\n",
    "                return 0\n",
    "            return res*-1    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        simbol=''\n",
    "        str_x=str(x)\n",
    "        if str_x[0]=='-':\n",
    "            simbol='-'\n",
    "            str_x=str_x[1:]\n",
    "        x=int(str_x)\n",
    "        \n",
    "        out=int(simbol+str_x[::-1])\n",
    "        if abs(out)>(pow(2,31)-1):\n",
    "            return 0\n",
    "        return out\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:        \n",
    "        re=0  \n",
    "        x_=abs(x)\n",
    "        while x_>0:\n",
    "            a=x_%10\n",
    "            x_=x_//10\n",
    "            re=re*10+a\n",
    "            print(re)\n",
    "        return 0 if (re>pow(2,31)-1)|(re<0-pow(2,31)) else (re if x>0 else 0-re)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        if x<0:\n",
    "            sym=0\n",
    "            x=abs(x)\n",
    "        else:\n",
    "            sym=1\n",
    "        length=len(str(x))\n",
    "        num=0\n",
    "        yushu=x\n",
    "        for i in range(length):\n",
    "            #注意python的幂运算\n",
    "            shang=int(yushu/(10**(length-i-1)))\n",
    "            print(shang,i)\n",
    "            yushu=yushu%(10**(length-i-1))\n",
    "            num+=shang*(10**(i))\n",
    "        if sym:\n",
    "            if num<2**31-1:\n",
    "                return num\n",
    "            else:\n",
    "                return 0\n",
    "        else:\n",
    "            if num<2**31:\n",
    "                return -num\n",
    "            else:\n",
    "                return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import platform\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        # p = platform.architecture()[0][:2]\n",
    "        a = pow(2, 31)\n",
    "        a1 = a -1\n",
    "        a2 = 0 - a\n",
    "        if a2 <= x <= a1:\n",
    "            s = str(x)\n",
    "            if s.startswith('-'):\n",
    "                res = '-' + s[1::][::-1]\n",
    "                d = int(res)\n",
    "                if a2 <= d <= a1: \n",
    "                    return d\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                d = int(s[::-1])\n",
    "                if a2 <= d <= a1: \n",
    "                    return d\n",
    "                else:\n",
    "                    return 0\n",
    "        else:\n",
    "            print(\"溢出\")\n",
    "            return 0\n",
    "    \n",
    "    \n",
    "test = Solution()\n",
    "print('-----', test.reverse(1534236469))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import pow\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        if x == 0:\n",
    "            return 0\n",
    "\n",
    "        result = 0\n",
    "\n",
    "        negative = False\n",
    "        if x < 0:\n",
    "            negative = True\n",
    "            x *= -1\n",
    "\n",
    "        digit = pow(10, len(str(x))-1)\n",
    "\n",
    "        while x != 0:\n",
    "            result += (x % 10) * digit\n",
    "            x = x // 10\n",
    "            digit /= 10\n",
    "\n",
    "        if negative:\n",
    "            result *= -1\n",
    "\n",
    "        if result > pow(2, 31)-1 or result < -pow(2, 31):\n",
    "            return 0\n",
    "\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        y, res = abs(x), 0\n",
    "        of = (1<<31) -1 if x > 0 else (1<<31)\n",
    "        while y != 0:\n",
    "            tmp = y % 10\n",
    "            res = res*10 + tmp\n",
    "            y = y // 10\n",
    "        if res > of:\n",
    "            return 0\n",
    "        return res if x > 0 else 0-res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        # if x < -(2**31-1):return 0\n",
    "\n",
    "        if x >= 0:\n",
    "            sign = 1\n",
    "            s = str(x)\n",
    "        else:\n",
    "            sign = -1\n",
    "            s = str(x)[1:]\n",
    "\n",
    "        y = sign*int(s[::-1])\n",
    "\n",
    "        if not -2**31 <= y <= 2**31 - 1 :\n",
    "            return 0\n",
    "        else:\n",
    "            return y\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        s=str(x)\n",
    "        n=len(s)\n",
    "        if s[0]=='-':\n",
    "            res='-'\n",
    "            n-=1\n",
    "        else:\n",
    "            res=''\n",
    "        for i in range(n):\n",
    "            res+=s[-i-1]\n",
    "        res=int(res)\n",
    "        if res<-2**31 or res>2**31-1:\n",
    "            res=0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        maxx = pow(2,31)-1\n",
    "        maxx_rm = maxx%10\n",
    "        maxx_div = int(maxx/10)\n",
    "        minx = -1*pow(2,31)\n",
    "        mimx_rm = minx%-10\n",
    "        minx_div = minx//-10*-1\n",
    "        res = 0\n",
    "        # print(maxx_div,maxx_rm,minx_div,mimx_rm)\n",
    "        while (x>0):\n",
    "            rm = x%10\n",
    "            print(x,res,rm)\n",
    "            if res>maxx_div or (res==maxx_div and rm>maxx_rm):\n",
    "                return 0\n",
    "            elif res<minx_div or (res==minx_div and rm<mimx_rm):\n",
    "                return 0\n",
    "            res = res*10+rm\n",
    "            x = x//10\n",
    "        while (x<0):\n",
    "            rm = x%-10\n",
    "            print(x,res,rm)\n",
    "            if res>maxx_div or (res==maxx_div and rm>maxx_rm):\n",
    "                return 0\n",
    "            elif res<minx_div or (res==minx_div and rm<mimx_rm):\n",
    "                return 0\n",
    "            res = res*10+rm\n",
    "            x = x//-10*-1\n",
    "            print(x)\n",
    "        return res\n",
    "    # def reverse(self, x: int) -> int:\n",
    "    #     if x==0:\n",
    "    #         return 0\n",
    "    #     abs_minx = list(str(pow(2,31)))\n",
    "    #     abs_maxx = list(str(pow(2,31)-1))\n",
    "    #     xstr = str(abs(x))\n",
    "    #     flag = int(x/abs(x))\n",
    "    #     xlist = list(xstr)\n",
    "    #     xlist_re = xlist[::-1]\n",
    "    #     new_xstr = ''.join(xlist_re)\n",
    "    #     # print('newstr:',new_xstr)\n",
    "    #     if len(xlist)<10:\n",
    "    #         return flag*int(new_xstr)\n",
    "    #     elif flag > 0:\n",
    "    #         for i in range(len(abs_maxx)):\n",
    "    #             if int(new_xstr[i])<int(abs_maxx[i]):\n",
    "    #                 # print(new_xstr[i],abs_maxx[i])\n",
    "    #                 return flag*int(new_xstr)\n",
    "    #             elif int(new_xstr[i])>int(abs_maxx[i]):\n",
    "    #                 # print(new_xstr[i],abs_maxx[i])\n",
    "    #                 return 0\n",
    "    #     else:\n",
    "    #         for i in range(len(abs_minx)):\n",
    "    #             if int(new_xstr[i])<int(abs_minx[i]):\n",
    "    #                 return flag*int(new_xstr)\n",
    "    #             elif int(new_xstr[i])>int(abs_minx[i]):\n",
    "    #                 return 0\n",
    "    #     return flag*int(new_xstr)\n",
    "\n",
    "        \n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        INT_MAX = (1 << 31) - 1\n",
    "        INT_MIN = -1 << 31\n",
    "        res = 0\n",
    "        while x != 0:\n",
    "            remain = x % 10\n",
    "            if x < 0 and remain != 0:\n",
    "                remain -= 10\n",
    "            if res == INT_MAX // 10 and remain >= 8:\n",
    "                return 0\n",
    "            if res == INT_MIN // 10 and remain <= 8:   \n",
    "                return 0\n",
    "            res = res * 10\n",
    "            print(remain)\n",
    "            x = (x - remain) // 10\n",
    "            res += remain\n",
    "        if res > INT_MAX or res < INT_MIN:   \n",
    "            return 0\n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        s = str(abs(x))\n",
    "        temp = s[::-1]\n",
    "        if x >= 0:\n",
    "            temp = int(temp)\n",
    "        else:\n",
    "            temp = -int(temp)\n",
    "        if temp > (2**31 - 1) or temp < ((-2)**31):\n",
    "            return 0\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        s = str(x)  \n",
    "        if s[0] == '-':\n",
    "            s_rev = s[0] + s[-1:-len(s):-1]  \n",
    "        else:\n",
    "            s_rev = s[::-1]  \n",
    "        x_rev = int(s_rev)  \n",
    "        if -2**31 <= x_rev <= 2**31 - 1:\n",
    "            return x_rev\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        x_abs_str = str(abs(x))\n",
    "        res = 0\n",
    "        for i in range(len(x_abs_str)-1, -1, -1):\n",
    "            cur = int(x_abs_str[i])\n",
    "            res = res * 10 + cur\n",
    "        if res < -(2**31) or res > (2**31 - 1):\n",
    "            res = 0\n",
    "        return res if x>=0 else -res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
